// 496.[单调栈]下一个更大元素I.
// https://leetcode.cn/problems/next-greater-element-i/
//求右边的第一大元素，
// nums1中数字x的下一个更大元素是指 x 在nums2中对应位置右侧的第一个比x大的元素。
//给你两个没有重复元素的数组nums1和nums2，下标从0开始计数，其中nums1 是 nums2
//的子集。
//对于每个0<=i<nums1.length，找出满足nums1[i]==nums2[j]的下标j，并且在nums2确定nums2[j]的下一个更大元素。
//如果不存在下一个更大元素，那么本次查询的答案是-1。
//返回一个长度为
// nums1.length的数组ans作为答案，满足ans[i]是如上所述的下一个更大元素。
//输入：nums1=[4,1,2],nums2=[1,3,4,2].
//输出：[-1,3,-1]
//输入：nums1=[2,4],nums2=[1,2,3,4].
//输出：[3,-1]
//需要先知道当前元素右边的数字，所以从右边开始遍历比较方便（重要）
//解法1思想:
//从右往左遍历，循环出栈后，就认为栈顶元素就是下一个最大的值。
//过程：
//栈空，2入栈
// 4>2，2出栈，栈为空，没有比4大的元素，4入栈
// 3<4，且栈不空，栈顶元素4即为3的右边第一大元素，3入栈
// 1<3，且栈不空，栈顶元素3即为1的右边第一大元素，1入栈
//解法2思想:
//仍然从左往右遍历，当栈不空或者栈顶元素比当前元素小，循环出栈，出栈元素的下一个最大值即为当前遍历的值。
//过程：栈空，1入栈
//栈不空且3 > 1，1出栈，1的下一个最大元素为3，3入栈
//栈不空且4 > 3，3出栈，3的下一个最大元素为4，4入栈
//栈不空，但2 < 4，4的下一个最大元素为-1，2入栈
//栈内元素全部没有右边的下一个最大元素，都为-1

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
 public:
  vector<int> nextGreaterElement_eg(vector<int>& nums1, vector<int>& nums2) {
    int len1 = nums1.size();
    int len2 = nums2.size();
    vector<int> res(len1);
    for (int i = 0; i < len1; ++i) {
      int j = 0;
      while (j < len2 && nums2[j] != nums1[i]) {
        ++j;
      }
      int k = j + 1;
      while (k < len2 && nums2[k] < nums2[j]) {
        ++k;
      }
      res[i] = k < len2 ? nums2[k] : -1;
    }
    return res;
  }

  // 单调栈，右边第一个比自己大的值
  vector<int> nextGreaterElement_me(vector<int>& vtFind, vector<int>& vtRaw) {
    const int MIN_VAL = -1;
    vector<int> vtRGreater(vtRaw.size(), MIN_VAL);  // default -1
    map<int, int> mapRightGreater;                  // number, right greater
    // 单调栈, 数组非空
    stack<size_t> stkNum2;  // index of vtRaw
    stkNum2.push(0);
    for (size_t i = 1; i < vtRaw.size(); i++) {
      while (!stkNum2.empty() && vtRaw[stkNum2.top()] > vtRaw[i]) {
        mapRightGreater[vtRaw[stkNum2.top()]] = vtRaw[i];  // insert map
        vtRGreater[stkNum2.top()] = vtRaw[i];              // set vector
        stkNum2.pop();
      }
      stkNum2.push(i);
    }

    // print    for (auto n : vtRGreater) PF("%d,", n); PF("\n");

    // 输出 需要查询某个值的右大值,右边第一个比自己大的值
    vector<int> ans;
    for (auto n : vtFind) {
      if (mapRightGreater.count(n) > 0) {
        ans.push_back(mapRightGreater[n]);
      } else {
        ans.push_back(MIN_VAL);
      }
    }
    return ans;
  }

  // 单调栈，最基础，简洁逻辑算法
  vector<int> nextGreaterElement_basic(vector<int>& vt) {
    vector<int> res(vt.size(), -1);
    stack<size_t> stk;  // vt index
    stk.push(0);
    for (size_t i = 1; i < vt.size(); i++) {
      while (!stk.empty() && vt[i] > vt[stk.top()]) {
        res[stk.top()] = vt[i];
        stk.pop();
      }
      stk.push(i);
    }
    return res;
  }
};

int main() {
  Solution sol;
  vector<int> nums1 = {4, 1, 2};
  vector<int> nums2 = {1, 3, 4, 2};

  for (auto n : nums1) PF("%d,", n);
  PF("\n");
  for (auto n : nums2) PF("%d,", n);
  PF("\n");
  PF("\n");

  // {-1,3,-1};
  vector<int> nums3 = sol.nextGreaterElement_me(nums1, nums2);
  for (auto n : nums3) {
    printf("%d,", n);
  }
  printf("\n");
  return 0;
}
